/*
动态规划求解：
We define dp[i][j] as following:
dp[i][j] = {true|if the substring s[i]…s[j] is a palindromeotherwise, false} 
Therefore:
dp[i][j] = (dp[i+1][j-1] && s[i]==s[j] )

The base cases are:
dp[i][i] = true
dp[i][i+1] = ( s[i]==s[i+1] )
*/
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    string longestPalindrome(string s)
    {
        if (s.empty())
            return "";
        //initial
        //bool map[1000][1000];
        //原先的声明会导致OJ出错，leetcode所用的case都在同一对象实例中运行
        //之前对map的初始化会影响后续的结果
        int size = s.size();
        bool map[size][size];
        memset(map, 0, sizeof(bool) * (size * size));
        int max_length = 1;
        string sub_string = "";
        sub_string = s[0];
        for (int i = 0; i < s.size(); i++) {
            map[i][i] = true;
            if (s[i] == s[i + 1] && i + 1 < s.size()) {
                map[i][i + 1] = true;
                max_length = 2;
                sub_string = s.substr(i, max_length);
            }
        }
        //dp & find longest substring
        //求解顺序与范围可根据画图来判断，求解当前状态时其必须保证其转移依赖状态已经得出
        for (int i = s.size() - 3; i >= 0; i--) {
            for (int j = i + 2; j < s.size(); j++) {
                if (map[i + 1][j - 1] && s[i] == s[j]) {
                    map[i][j] = true;
                    if (j - i + 1 > max_length) {
                        max_length = j - i + 1;
                        sub_string = s.substr(i, max_length);
                    }
                } else
                    map[i][j] = false;
            }
        }
        return sub_string;
    }
};

int main(int argc, char const* argv[])
{
    Solution temp;
    cout << temp.longestPalindrome("abcdbbfcba") << endl;
    cout << temp.longestPalindrome("aaabaaaa") << endl;
    cout << temp.longestPalindrome("aaabaaa") << endl;
    cout << temp.longestPalindrome("avdjdndjdndjodfk") << endl;
    return 0;
}